package hehe.test;

import java.util.Random;

public class Sort {

	
	public static void main(String[] args) {
		int[] a = new int[100];
		for(int i = 0; i < a.length; ++i) {
			a[i] = i+1;
		}
		
		shuffle(a, new Random());
		printArray(a);
		/*mergeSort(a, 0, a.length -1);*/
		mergeSortNonRec(a);
		printArray(a);
	}

	public static void mergeSort(int[] a, int lo, int hi) {
		if(hi <= lo) return;
		int mid = (lo + hi) /2;
		mergeSort(a, lo, mid);
		mergeSort(a, mid+1, hi);
		//mergeArray(a, lo, mid, hi);
	}
	
	public static void mergeSortNonRec(int[] a) {
		int N = a.length;
		int[] temp = new int[N];
		for(int i = 1; i < N; i += i) {
			for(int j = 0; j < N - i; j += i + i) {
				mergeArray(a, temp, j, j + i - 1, Math.min(j + i + i - 1, N - 1));
			}
		}
	}
	
	private static void mergeArray(int[] a, int[] temp, int lo, int mid, int hi) {
		int i = lo, j = mid + 1;
		//int[] temp = new int[a.length];
		for(int k = lo; k<=hi; k++) temp[k] = a[k];

		for(int k = lo; k <= hi; k++) {
			if(i > mid) a[k] = temp[j++];
			else if (j > hi) a[k] = temp[i++];
			else if (temp[j] < temp[i]) a[k] = temp[j++];
			else a[k] = temp[i++];
		}
	}

	private static void shuffle(int[] array, Random r) {
		for(int i = array.length; i > 0; i--) {
			swap(array, i - 1, r.nextInt(i));
		}
	}
	private static void swap(int[] array, int a, int b) {
		int temp = array[a];
		array[a] = array[b];
		array[b] = temp;
	}
	private static void printArray(int[] array) {
		System.out.print("array = [");
		for(int i = 0 ;i < array.length; ++i) {
			if(i == array.length -1) System.out.println(array[i]+ "]");
			else System.out.print(array[i] + " , ");
		}
	}
}
